// 非负数组前k个最小的子序列累加和
// 给定一个数组nums，含有n个数字，都是非负数
// 给定一个正数k，返回所有子序列中累加和最小的前k个累加和
// 子序列是包含空集的
// 1 <= n <= 10^5
// 1 <= nums[i] <= 10^6
// 1 <= k <= 10^5
// 注意这个数据量，用01背包的解法是不行的，时间复杂度太高了
// 对数器验证

#include <bits/stdc++.h>

using namespace std;

// 暴力方法
// 得到所有子序列的和
void f1(vector<int>& nums, int i, int sum, vector<int>& ans)
{
    if(i == nums.size())
    {
        ans.push_back(sum);
        return;
    }
    f1(nums, i + 1, sum, ans);
    f1(nums, i + 1, sum + nums[i], ans);
}

// 暴力方法
// 为了验证
vector<int> topKSum1(vector<int>& nums, int k)
{
    vector<int> ans;
    f1(nums, 0, 0, ans);
    sort(ans.begin(), ans.end());
    return vector<int>(ans.begin(), ans.begin() + k);
}

// 01背包来实现
// 这种方法此时不是最优解
// 因为n很大，数值也很大，那么可能的累加和就更大
// 时间复杂度太差
vector<int> topKSum2(vector<int>& nums, int k)
{
    int sum = accumulate(nums.begin(), nums.end(), 0);
    // dp[i][j]
    // 1) dp[i-1][j]
    // 2) dp[i-1][j-nums[i]]
    int dp[sum + 1];
    memset(dp, 0, sizeof dp);
    dp[0] = 1;
    for(int num : nums)
    {
        for(int j = sum; j >= num; --j)
        {
            dp[j] += dp[j - num];
        }
    }
    vector<int> ans(k);
    int index = 0;
    for(int j = 0; j <= sum && index < k; ++j)
    {
        for(int i = 0; i < dp[j] && index < k; ++i)
        {
            ans[index++] = j;
        }
    }
    return ans;
}

// 正式方法
// 用堆来做是最优解，时间复杂度O(n * log n) + O(k * log k)
vector<int> topKSum3(vector<int>& nums, int k)
{
    sort(nums.begin(), nums.end());
    // (子序列的累加和的相反数，子序列的最右下标)
    // 这样做是因为标准库中是大根堆，那么加上一个符号就变成小根堆了
    // 不过弹出堆顶元素进行使用时，要将负数转变成正数
    priority_queue<pair<int, int>> heap;
    heap.emplace(-nums[0], 0);
    vector<int> ans(k);
    for(int i = 1; i < k; ++i)
    {
        auto [negSum, right] = heap.top();
        heap.pop();
        ans[i] = -negSum;
        if(right + 1 < nums.size())
        {
            // 不要 nums[right]
            heap.emplace(negSum + nums[right] - nums[right + 1], right + 1);
            // 要 nums[right]
            heap.emplace(negSum - nums[right + 1], right + 1);
        }
    }
    return ans;
}

// 为了测试
// 生成长度为n，值在[-v, +v]之间的随机数组
vector<int> randomArray(int len, int value)
{
    vector<int> arr(len);
    for (int i = 0; i < len; ++i)
    {
        arr[i] = rand() % value;
    }
    return arr;
}

// 为了测试
bool equals(vector<int>& ans1, vector<int>& ans2)
{
    if(ans1.size() != ans2.size()) return false;
    for(int i = 0; i < ans1.size(); ++i)
    {
        if(ans1[i] != ans2[i]) return false;
    }
    return true;
}

// 为了测试
// 对数器
int main()
{
    srand(time(nullptr));
    int n = 15;
    int v = 40;
    int testTime = 10000;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTime; i++)
    {
        int len = rand() % n + 1;
        vector<int>&& nums = randomArray(len, v);
        int k = rand() % ((1 << len) - 1) + 1;
        vector<int>&& ans1 = topKSum1(nums, k);
        vector<int>&& ans2 = topKSum2(nums, k);
        vector<int>&& ans3 = topKSum3(nums, k);
        if(!equals(ans1, ans2) || !equals(ans1, ans3))
        {
            cout << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;

    return 0;
}